#include <iostream>

#define MaxVertexNum 100           // the max numbers of vertexes
#define INFINITY 1000;             // the max weight for edge weight

typedef char VertexType;           // the node type for vertexes
typedef int EdgeType;              // the edge type for edges

// the common graph data structure
typedef struct {
    VertexType Vex[MaxVertexNum];              // the table for vextex;
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // the adjoint matrix for edges
    int vexnum, arcnum;                        // the amount for vertex and edges in this graph
} AdjoinMatrixGraph;

// the adjoin list representation for graph
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} AdjoinListGraph;

typedef struct ArcNode{
    int adjvex;            // the edge
    struct ArcNode *next;  // points the next arcnode
    // InfoType info;      // the information for this edge
}ArcNode;

typedef struct VNode{
    VertexType data;      // the data for this vertex
    ArcNode *first;       // the first node for this vertex
}VNode, AdjList[MaxVertexNum];

// the supplementary adjoin list for digraph representation
typedef struct {
    NewAdjoinList vertices;
    int vexnum, arcnum;
} DiGraph;

typedef struct NewArcNode {
    int tailvex;           // the identifier of the tail vertex of this edge
    int headvex;           // the identifier of the head vertex of this edge

    NewArcNode *hlink;     // the edge node which has the same headvex identifier
    NewArcNode *tlink;     // the edge node which has the same tailvex identifier

    // InfoType info;      // the information for this edge
} NewArcNode;

typedef struct NewVexNode{
    VertexType data;           // the data for this vertex
    NewArcNode *firstin;       // the first in-edge for this vertex
    NewArcNode *firstout;      // the first out-edge for this vertex
}NewVexNode, NewAdjoinList[MaxVertexNum];


